package BackTracking;

import Utils.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class binaryTreePaths {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> path = new ArrayList<>();
        if (root == null) {
            return path;
        }
        List<Integer> values = new ArrayList<>();
        backTracking(root, values, path);
        return path;
    }

    private void backTracking(TreeNode node, List<Integer> values, List<String> paths) {
        if (node == null) {
            return;
        }
        values.add(node.val);
        if (isLeaf(node)) {
            paths.add(buildPaths(values));
        } else {
            backTracking(node.left, values, paths);
            backTracking(node.right, values, paths);
        }
        values.remove(values.size() - 1);
    }

    private boolean isLeaf(TreeNode node) {
        if (node.left == null && node.right == null) {
            return true;
        }
        return false;
    }

    private String buildPaths(List<Integer> values) {
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < values.size(); i++) {
            builder.append(values.get(i));
            if (i != values.size() - 1) {
                builder.append("->");
            }
        }
        return builder.toString();
    }
}
